package main.java.leetcode.editor.cn;
//2022-03-15 21:20:13
//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 
//
// 实现 MinStack 类: 
//
// 
// MinStack() 初始化堆栈对象。 
// void push(int val) 将元素val推入堆栈。 
// void pop() 删除堆栈顶部的元素。 
// int top() 获取堆栈顶部的元素。 
// int getMin() 获取堆栈中的最小元素。 
// 
//
// 
//
// 示例 1: 
//
// 
//输入：
//["MinStack","push","push","push","getMin","pop","top","getMin"]
//[[],[-2],[0],[-3],[],[],[],[]]
//
//输出：
//[null,null,null,null,-3,null,0,-2]
//
//解释：
//MinStack minStack = new MinStack();
//minStack.push(-2);
//minStack.push(0);
//minStack.push(-3);
//minStack.getMin();   --> 返回 -3.
//minStack.pop();
//minStack.top();      --> 返回 0.
//minStack.getMin();   --> 返回 -2.
// 
//
// 
//
// 提示： 
//
// 
// -231 <= val <= 231 - 1 
// pop、top 和 getMin 操作总是在 非空栈 上调用 
// push, pop, top, and getMin最多被调用 3 * 104 次 
// 
// Related Topics 栈 设计 
// 👍 1219 👎 0

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

class Solution {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        MinStack solution = new Solution().new MinStack();
        solution.push(512);
        solution.push(-1024);
        solution.push(-1024);
        solution.push(512);
        solution.pop();
        ;
        System.out.println(solution.getMin());
        solution.pop();
        System.out.println(solution.getMin());
        solution.pop();
        System.out.println(solution.getMin());
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class MinStack {
        long min;
        Stack<Long> stack = new Stack<>();

        public void push(int x) {
            if (stack.isEmpty()) {
                stack.push(0L);
                min = x;
            } else {
                //这里入栈的是入栈的值和最小值的差值，有可能为负，也有可能为正。
                stack.push(x - min);
                if (x < min)
                    min = x;
            }
        }

        public void pop() {
            if (stack.isEmpty())
                return;
            long pop = stack.pop();
            //因为入栈的是差值，当出栈的为负数的时候，说明栈中最小值已经出栈了，
            //这里要重新更新最小值
            if (pop < 0)
                min -= pop;
        }

        public int top() {
            long top = stack.peek();
            if (top > 0) {
                //栈顶元素如果是正的，说明栈顶元素压栈的时候是比栈中最小值大的，根据
                //top=x - min，可以计算x=top+min
                return (int) (top + min);
            } else {
                //当栈顶元素是负数的时候，说明栈顶元素压栈的时候是比栈中最小值小的，
                //而压栈完之后他会更新最小值min，所以如果在使用上面公式肯定是不行
                //的。如果栈顶元素压栈的时候比最小值小，他会更新最小值，这个最小值
                //就是我们要压栈的值，所以这里直接返回min就行了。
                return (int) (min);
            }
        }

        public int getMin() {
            return (int) min;
        }
    }

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
